package com.linwen.excise.leetcode;

/**
 * @ClassName _LCR170逆序对
 * @Description TODO
 * @Author zero
 * @DATE 2024/8/11 2:39 PM
 * @Version 1.0
 */
public class _LCR170逆序对 {
    public static void main(String[] args) {
        int[] arr = new int[]{9, 7, 5, 4, 6};
        int[] arr2 = new int[]{};
        System.out.println(reversePairs(arr));
        System.out.println(reversePairs2(arr2));
    }

    public static int reversePairs(int[] record) {
        int result = 0;
        for (int i = 0; i < record.length; i++) {
            for (int j = i + 1; j < record.length; j++) {
                if (record[i] > record[j]) {
                    result++;
                }
            }
        }
        return result;
    }

    public static int reversePairs2(int[] record) {
        return reversePairs2(0, record.length - 1, record);
    }

    public static int reversePairs2(int left, int right, int[] record) {
        if (left >= right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        int leftCount = reversePairs2(left, mid, record);
        int rightCount = reversePairs2(mid + 1, right, record);
        int mergeCount = merge(left, mid, right, record);
        return leftCount + rightCount + mergeCount;
    }

    private static int merge(int left, int mid, int right, int[] record) {
        int result = 0;
        int[] temp = new int[right - left + 1];
        int p0 = left;
        int p1 = mid + 1;
        int k = 0;
        while (p0 <= mid && p1 <= right) {
            // 因为两边都有序，所以当p0位置元素大于p1位置元素时，则p0位置元素以后的元素都大于p1位置元素，所以个数就是mid-p0+1
            result += record[p0] > record[p1] ? mid - p0 + 1 : 0;
            temp[k++] = record[p0] <= record[p1] ? record[p0++] : record[p1++];
        }
        while (p0 <= mid) {
            temp[k++] = record[p0++];
        }
        while (p1 <= right) {
            temp[k++] = record[p1++];
        }
        for (int i = 0; i < temp.length; i++) {
            record[left + i] = temp[i];
        }
        return result;
    }
}
